前端面试和笔试中被问到最多的算法可能就是各种排序算法了，算法并不难，平时经常用到，但很多时候很少会去认真考虑算法优劣性和适应场景，真正一个一个去分析也需要花不少时时间，所以趁年末有空，不如再复习一遍排序算法。
所有排序算法读者可自行尝试coding，想看源码戳这里。此文配合源码体验更佳！
排序算法评价标准时间复杂度一个算法语句总的执行次数是关于问题规模N的某个函数，记为f(N)，N称为问题的规模。语句总的执行次数记为T(N)，当N不断变化时，T(N)也在变化，算法执行次数的增长速率和f(N)的增长速率相同。
则有T(N) = O(f(N))，这称作算法的渐进时间复杂度，简称时间复杂度。
最坏时间复杂度、最好时间复杂度和平均时间复杂度最坏时间复杂度最坏情况下的时间复杂度称最坏时间复杂度，一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比任何更长。
平均时间复杂度平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间，设每种情况的出现的概率为pi,平均时间复杂度则为sum(pi*f(n)) 。
最好时间复杂度最理想情况下的时间复杂度称最好时间复杂度。
空间复杂度空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。
稳定性稳定的算法在排序的过程中不会改变元素彼此的位置的相对次序，反之不稳定的排序算法经常会改变这个次序,这是我们不愿意看到的。
我们在使用排序算法或者选择排序算法时,更希望这个次序不会改变,更加稳定,所以排序算法的稳定性,是一个特别重要的参数衡量指标依据。
内排序、外排序内排序：所有排序操作都在内存中完成，适用于数据规模不是特别大的情况；外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；
各排序算法总结对算法原理很熟悉的同学可以直接记忆这张表。
图片名词解释：
n: 数据规模k:“桶”的个数In-place: 占用常数内存，不占用额外内存Out-place: 占用额外内存一、冒泡排序（Bubble Sort）算法描述冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个相邻元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
算法思路具体算法描述如下：
比较相邻的元素。如果第一个比第二个大，就交换它们两个；对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；针对所有的元素重复以上的步骤，除了最后一个；重复步骤1~3，直到数组有序，排序完成。算法实现let bubbleSort = arr => { for (let i = 0; i < arr.length; i++) {for (let j = 0; j < arr.length - i - 1; j++) { if (arr[j] > arr[j + 1]) {let temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp; }} } return arr;};算法分析平均时间复杂度: T(n) = O(n²)最坏时间复杂度: T(n) = O(n²)：当输入的数据是反序时最好时间复杂度: T(n) = O(n)：当输入的数据已经有序时，只需遍历一遍用于确认数据已有序。空间复杂度: O(1)稳定性: 稳定
算法改进思路改进思路一：设置一标志flag，当一趟遍历过程中发生元素交换时改变flag值，而某趟当flag值没有改变，则代表数组已经有序，无需再继续排序。改进思路二： 设置一标志性变量pos，用于记录每趟排序中最后一次进行交换的位置。由于pos位置之后的记录均已交换到位,故在进行下一趟排序时只要扫描到pos位置即可。改进思路三：传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值,我们考虑利用在每趟排序中进行正向和反向两遍冒泡的方法一次可以得到两个最终值(最大者和最小者) , 从而使排序趟数几乎减少了一半。算法动图演示二、简单选择排序（insertion Sort）算法描述选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
算法思路具体算法描述如下：n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：
初始状态：无序区为R[1..n]，有序区为空；第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；n-1趟结束，数组有序化了。算法实现let selectSort = arr => { for (let i = 0; i < arr.length; i++) {Let min = arr[i]; // 初始化最小值为第一个元素let index = i; // 最小值下标for (let j = i + 1; j < arr.length; j++) { if (arr[j] < min) { // 发现更小的数则交换位置min = arr[j];index = j; }}// 将当前趟最小值移动至其最终位置let temp = arr[i];arr[i] = min;arr[index] = temp; }};算法分析选择排序是时间复杂度表现最稳定的排序算法之一，无论什么数据进去都是O(n²) 的时间复杂度…..所以用到它的时候，数据规模越小越好。这也是一般人想到最多的简单算法，简单粗暴。平均时间复杂度: T(n) = O(n²)最坏时间复杂度: T(n) = O(n²)最好时间复杂度: T(n) = O(n²)空间复杂度: O(1)稳定性: 不稳定
算法改进思路性能表现实在太稳定了，一般改进思路可以从空间换时间角度切入，减少比较次数。
算法动图演示三、插入排序算法描述插入排序（insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
如果你会打扑克牌，你在抓牌整理牌时，已经无意识地用到了插入排序。
算法思路一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
从第一个元素开始，该元素可以认为已经被排序；取出下一个元素，在已经排序的元素序列中从后向前扫描；如果该元素（已排序）大于新元素，将该元素移到下一位置；重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；将新元素插入到该位置后；重复步骤2~5。算法实现let insertSort = arr => { for (let i = 1; i < arr.length; i++) {let key = arr[i];let j = i - 1;while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--;}arr[j + 1] = key; } return arr;};算法分析平均时间复杂度: T(n) = O(n²)最坏时间复杂度: T(n) = O(n²)：输入数组按降序排列（完全逆序）最好时间复杂度: T(n) = O(n)：输入数组按升序排列（基本有序）空间复杂度: O(1)稳定性：稳定
算法改进思路改进思路一：查找插入位置时使用二分查找的方式，减少比较次数。算法动图演示四、希尔排序算法描述1959年Shell发明； 第一个突破O(n²)的排序算法；是简单插入排序的改进版；它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序
算法思路该方法实质上是一种分组插入方法，希尔排序是基于插入排序的以下两点性质而提出改进方法的：
插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：
1. 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；2. 按增量序列个数k，对序列进行k 趟排序；3. 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。算法实现let shellSort = function (arr) { let len = arr.length, temp, gap = 1; // 动态定义间隔序列 while (gap < len / 5) {gap = gap * 5 + 1; } for (gap; gap > 0; gap = Math.floor(gap / 5)) {for (let i = gap; i < len; i++) { temp = arr[i]; for (let j = i - gap; j >= 0 && arr[j] > temp; j -= gap) {arr[j + gap] = arr[j]; } arr[j + gap] = temp;} } return arr;}算法分析平均时间复杂度：T(n) = O(n^1.5)最坏时间复杂度：T(n) = O(nlog²n）空间复杂度: O(1)稳定性: 不稳定，由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。算法改进思路Shell排序的执行时间依赖于增量序列，好的增量序列的共同特征：① 最后一个增量必须为1；② 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。有人通过大量的实验，给出了较好的结果：当n较大时，比较和移动的次数约在nl.25到1.6n1.25之间。
但是Shell排序的时间性能显然优于直接插入排序，希尔排序的时间性能优于直接插入排序的原因：
当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。当n值较小时，n 和 n² 的差别也较小，即直接插入排序的最好时间复杂度 O(n) 和最坏时间复杂度 O(n²) 差别不大。在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量di逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按di-1作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。因此，希尔排序在效率上较直接插入排序有较大的改进。
使用建议：不需要大量的辅助空间，和归并排序一样容易实现。希尔排序是基于插入排序的一种算法， 在此算法基础之上增加了一个新的特性，提高了效率。希尔排序没有快速排序算法快 O(n(logn))，因此中等大小规模表现良好，对规模非常大的数据排序不是最优选择。但是比O(n²)复杂度的算法快得多。并且希尔排序非常容易实现，算法代码短而简单。 此外，希尔算法在最坏的情况下和平均情况下执行效率相差不是很多，与此同时快速排序在最坏的情况下执行的效率会非常差。专家们提倡，几乎任何排序工作在开始时都可以用希尔排序，若在实际使用中证明它不够快，再改成快速排序这样更高级的排序算法
算法演示五、归并排序算法描述和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(n log^n）的时间复杂度。代价是需要额外的内存空间。归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
算法思路归并排序算法思想：分而治之：
分解：把长度为n 的待排序列分解成 两个长度为n/2 的序列治理：对每个子序列分别调用归并排序，进行递归操作。当子序列长度为1 时，序列本身有序，停止递归合并：合并每个排序好的子序列算法实现let merge = (left, right) => { let result = []; while (left.length && right.length) {if (left[0] { let len = arr.length; if (len < 2) {return arr; } let middle = Math.floor(len / 2),left = arr.slice(0, middle),right = arr.slice(middle); return merge(mergeSort(left), mergeSort(right));}算法分析平均情况：T(n) = O(nlogn)最差情况：T(n) = O(nlogn)最佳情况：T(n) = O(n)空间复杂度: O(n)，归并排序需要一个与原数组相同长度的数组做辅助来排序稳定性: 稳定算法改进思路对小规模子数组使用插入排序。用不同的方法处理小规模数组能改进大多递归算法的性能，在小数组上上，插入排序可能比并归排序更快。测试数组是否有序。根据归并排序的特点，每次归并的两个小数组都是有序的，当 a[mid] { if (Array.isArray(array) && typeof left === 'number' && typeof right === 'number') {if (left < right) { let x = array[right], i = left - 1, temp; for (let j = left; j = 1; j—) {temp = array[0];array[0] = array[j];array[j] = temp;heapify(array, 0, —heapSize);}console.timeEnd('堆排序耗时');return array;} else {return 'array is not an Array!';}}/*方法说明：维护堆的性质@param arr 数组@param x数组下标@param len 堆大小*/function heapify(arr, x, len) {if (Object.prototype.toString.call(arr).slice(8, -1) === 'Array' && typeof x === 'number') {var l = 2 * x + 1, r = 2 * x + 2, largest = x, temp;if (l < len && arr[l] > arr[largest]) {largest = l;}if (r < len && arr[r] > arr[largest]) {largest = r;}if (largest != x) {temp = arr[x];arr[x] = arr[largest];arr[largest] = temp;heapify(arr, largest, len);}} else {return 'arr is not an Array or x is not a number!';}}算法分析调堆：O(h)建堆：O(n)循环调堆：O(nlogn)总运行时间T(n) = O(nlogn) + O(n) = O(nlogn)。对于堆排序的最好情况与最坏情况的运行时间，因为最坏与最好的输入都只是影响建堆的运行时间O(1)或者O(n)，而在总体时间中占重要比例的是循环调堆的过程，即O(nlogn) + O(1) =O(nlogn) + O(n) = O(nlogn)。因此最好或者最坏情况下，堆排序的运行时间都是O(nlogn)。而且堆排序还是 原地算法（in-place algorithm） 。
平均情况：T(n) = O(nlogn)最差情况：T(n) = O(nlogn)最佳情况：T(n) = O(nlogn)空间复杂度：O(1)稳定性：不稳定算法动图演示小结文章最后再对七大经典排序算法性能分析做一次小结，加深记忆。
稳定的排序：冒泡排序，插入排序，归并排序不稳定的排序：选择排序，堆排序，快速排序，希尔排序
平均时间复杂度T(n) = O(nlogn)：希尔排序，归并排序，快速排序，堆排序平均时间复杂度T(n) = O(n²)：冒泡排序，简单选择排序，插入排序
最好时间复杂度T(n) = O(n)：冒泡排序，插入排序最好时间复杂度T(n) = O(nlogn)：归并排序，快速排序，堆排序最好时间复杂度T(n) = O(n²)：简单选择排序
最坏时间复杂度T(n) = O(nlogn)：归并排序，堆排序最坏时间复杂度T(n) = O(n²)：冒泡排序，简单选择排序，插入排序，快速排序
空间复杂度O(1)：冒泡排序，简单选择排序，插入排序，希尔排序，堆排序空间复杂度O(n)：归并排序空间复杂度O(nlogn)：快速排序
参考：十大经典排序算法总结堆排序及其分析